Imagine the following scenario involving three parties: Alice, Bob and Carol. Alice cryptographically signs a message and gives the signed message to Bob. Bob wants to prove to a third party, Carol, that he possesses the message signed by Alice, but does not want to disclose the original signature to Carol. This scenario occurs often. It is not uncommon for an application to request that a service forward a digitally signed message from a user to another entity. For example, during online authentication: a service such as WINDOWS LIVE ID issues digitally signed authentication tickets in a format such as the Security Assertion Markup Language (SAML) to a user. The user presents the ticket to a relying party (“RP”) as proof of identity. The relying party, in turn, may need to invoke another service, which requires proof that the service is being invoked on behalf of the original user. Accordingly the relying party forwards the ticket. As another example, a user can authenticate his/her self to XBOX LIVE using a signed ticket from the WINDOWS LIVE ID service. XBOX LIVE in turn can call a third-party to request an action (e.g., call a voice carrier to provide voice communication between players), and forwards the ticket to the third party. The third party can verify that the action is on behalf of the original user by validating the signed ticket. A problem however is that the third party (e.g., the voice-carrier), using the signature, can impersonate the user. For example, the third party could make similar requests to other services on behalf of the user or in some cases, even impersonate the user back to XBOX LIVE. Thus, requesting a service to forward the signed message requires that the recipient of the signed message be trusted not to misuse or reuse the signed message.